package com.computer.fundamentals.datastructure;

import com.computer.fundamentals.datastructure.node.SingleLinkedNode;
import com.computer.util.Constant;
import com.computer.util.UniversalMethod;

public class SingleLinkedList {

    SingleLinkedNode head; // 虚拟的头节点，实际上是一个头部边界
    int size;

    public SingleLinkedList() { }

    public SingleLinkedList(SingleLinkedNode head_) {
        this.head = head_;
    }

    /**
     * 头插法
     */
    public void addFirst(int val) {
        SingleLinkedNode node = new SingleLinkedNode(val);
        node.next = head.next;
        head.next = node;
        size++;
    }

    /**
     * 头删法
     */
    public void removeFirst() {
        if (size <= 0) {
            throw new RuntimeException(Constant.LINKED_LIST_LENGTH_ZERO);
        }
        head.next = head.next.next;
        size--;
    }

    /**
     * 向位置i插入节点，i从1开始
     */
    public void insert(int idx, int val) {
        if (idx > size || idx < 1) {
            throw new RuntimeException(Constant.LINKED_LIST_INDEX_OUT_OF_RANGE);
        }
        SingleLinkedNode cur = head;
        while (idx > 1) {
            cur = cur.next;
            idx--;
        }
        SingleLinkedNode newNode = new SingleLinkedNode(val);
        newNode.next = cur.next;
        cur.next = newNode;
        size++;
    }

    /**
     * 删除位置i的节点，i从1开始
     */
    public void remove(int idx) {
        if (idx > size || idx < 1) {
            throw new RuntimeException(Constant.LINKED_LIST_INDEX_OUT_OF_RANGE);
        }
        SingleLinkedNode cur = head;
        while (idx > 1) {
            cur = cur.next;
            idx--;
        }
        cur.next = cur.next.next;
        size--;
    }

    /**
     * 反转链表，测试前往 https://leetcode-cn.com/problems/reverse-linked-list/
     */
    public SingleLinkedNode reverse(SingleLinkedNode head) {
        SingleLinkedNode cur = head, pre = null;
        while (cur != null) {
            SingleLinkedNode nextCur = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextCur;
        }
        return pre;
    }

    /**
     * K个一组反转链表
     */
    public SingleLinkedNode reverseKGroup(SingleLinkedNode head, int k) {
        if (k == 1) {
            return head;
        }
        SingleLinkedNode sentinel = new SingleLinkedNode(0, head);
        SingleLinkedNode curS = sentinel;
        SingleLinkedNode preS = sentinel;
        boolean flag = true;
        while (true) {
            // 获取数量为k的链表子组
            int count = k;
            while (count-- > 0) {
                curS = curS.next;
                if (curS == null) {
                    flag = false;
                    break;
                }
            }
            // 后续链表子组节点数量小于k
            if (!flag) {
                break;
            }
            // 断链并保留后续节点副本
            SingleLinkedNode copyNext = curS.next;
            curS.next = null;
            // 保留起始节点
            SingleLinkedNode start = preS.next;
            // 反转子组
            preS.next = reverse(start);
            start.next = copyNext;
            // 移动哨兵
            preS = start;
            curS = start;
        }

        return sentinel.next;
    }

    /**
     * 打印链表
     */
    public void printLinked() {
        SingleLinkedNode cur = head.next;
        while (cur != null) {
            if (cur.next != null) {
                System.out.print(cur.val + Constant.SINGLE_LINKED_LIST_SPLIT_SIGNAL);
            }
            else {
                System.out.print(cur.val);
            }
            cur = cur.next;
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        SingleLinkedList singleLinkedList = UniversalMethod.createSingleLinkedList(Constant.DEFAULT_LINKED_LIST_LENGTH);

        System.out.println("-------------------完整链表-------------------");
        singleLinkedList.printLinked();
        System.out.println("\n");

        System.out.println("-------------------头插法-------------------");
        singleLinkedList.addFirst(-1);
        singleLinkedList.printLinked();
        System.out.println("\n");

        System.out.println("-------------------删除头部节点-------------------");
        singleLinkedList.removeFirst();
        singleLinkedList.printLinked();
        System.out.println("\n");

        System.out.println("-------------------向链表某一个位置插入节点-------------------");
        singleLinkedList.insert(5, 100);
        singleLinkedList.printLinked();
        System.out.println("\n");

        System.out.println("-------------------删除某一个位置的节点-------------------");
        singleLinkedList.remove(5);
        singleLinkedList.printLinked();
        System.out.println("\n");

        System.out.println("-------------------K个一组翻转链表测试-------------------");
        SingleLinkedNode singleLinkedNode = singleLinkedList.reverseKGroup(singleLinkedList.head.next, 2);
        UniversalMethod.printSingleLinkedList(singleLinkedNode);

    }
}